package com.zs.letcode.top_interview_questions;

import java.math.BigInteger;

/**
 * 阶乘后的零
 * 给定一个整数 n，返回 n! 结果尾数中零的数量。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 3
 * 输出: 0
 * 解释:3! = 6, 尾数中没有零。
 * 示例2:
 * <p>
 * 输入: 5
 * 输出: 1
 * 解释:5! = 120, 尾数中有 1 个零.
 * 说明: 你算法的时间复杂度应为O(logn)。
 * <p>
 * 相关标签
 * 数学
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/x2we65/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/6/17 10:29
 */
public class Chapter69 {
    public static void main(String[] args) {

    }

    private static class Solution {
        /**
         * 方法一：计算阶乘
         */
        public int trailingZeroes(int n) {
            BigInteger nFactorial = BigInteger.ONE;
            for (int i = 2; i <= n; i++) {
                nFactorial = nFactorial.multiply(BigInteger.valueOf(i));
            }
            int zeroCount = 0;
            while (nFactorial.mod(BigInteger.TEN).equals(BigInteger.ZERO)) {
                nFactorial = nFactorial.divide(BigInteger.TEN);
                zeroCount++;
            }
            return zeroCount;
        }

        /**
         * 方法二：计算因子 5
         */
        public int trailingZeroes1(int n) {
            int zeroCount = 0;
            for (int i = 5; i <= n; i += 5) {
                int powerOf5 = 5;
                while (i % powerOf5 == 0) {
                    zeroCount += 1;
                    powerOf5 *= 5;
                }
            }
            return zeroCount;
        }

        /**
         * 方法三：高效的计算因子 5
         */
        public int trailingZeroes2(int n) {
            int zeroCount = 0;
            while (n > 0) {
                n /= 5;
                zeroCount += n;
            }
            return zeroCount;
        }
    }
}
